import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;//右孩子地址
        public TreeNode right;//左孩子地址

        public TreeNode(char val) {
            this.val = val;
        }

    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;//那么这个A就是根节点
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        //1.非空树才能打印
        if (root == null) return;
        //2.打印根
        System.out.print(root.val + " ");
        //3.打印左子树
        preOrder(root.left);
        //4.右子树
        preOrder(root.right);
    }

    //带有返回值的前序遍历
    //子问题
    /*public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        //放入根
        list.add(root.val);
        //左子树
        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        //右子树
        List<Integer> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }*/
    /*List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        //1.非空树才能打印
        if(root == null)
            return list;
        //2.存入list中
        list.add(root.val);
        //3.左子树
        preorderTraversal(root.left);
        //4.右子树
        preorderTraversal(root.right);
        return list;
    }*/
    public void inOrder(TreeNode root) {
        //1.非空树才能打印
        if (root == null) return;
        //2.打印左子树
        inOrder(root.left);
        //3.打印根
        System.out.print(root.val + " ");
        //4.右子树
        preOrder(root.right);
    }
    //有返回值的
    /*public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        //左子树
        List<Integer> Lifttree = postorderTraversal(root.left);
        ret.addAll(Lifttree);
        //右子树
        List<Integer> Righttree = postorderTraversal(root.right);
        ret.addAll(Righttree);
        //根
        ret.add(root.val);
        return ret;

    }*/

    //后续遍历
    public void postOrder(TreeNode root) {
        //1.非空树才能打印
        if (root == null) return;
        //2.打印左子树
        inOrder(root.left);
        //3.右子树
        preOrder(root.right);
        //4.打印根
        System.out.print(root.val + " ");
    }

    //有返回值的
    /*public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        //左子树
        List<Integer> Lifttree = inorderTraversal(root.left);
        ret.addAll(Lifttree);
        //根
        ret.add(root.val);
        //右子树
        List<Integer> Righttree = inorderTraversal(root.right);
        ret.addAll(Righttree);

        return ret;
    }*/

    //获取树中节点
    public int usedSize = 0;

    public int size(TreeNode root) {
        if (root == null) return usedSize;
        usedSize++;
        size(root.left);//左子树节点个数
        size(root.right);//右子树节点个数
        return usedSize;
    }

    //节点总数：左节点个数+右节点个数+根节点
    public int size2(TreeNode root) {
        if (root == null) return 0;

        int ret = size2(root.left) + size2(root.right) + 1;
        return ret;
    }

    //获取叶子节点个数
    public int getLeafNodeCount(TreeNode root) {
        int ret = 0;
        if (root == null) return ret;

        if (root.right == null && root.left == null) {
            return 1;
        }
        ret = getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
        return ret;
    }

    int ret = 0;

    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) return ret;
        if (root.right == null && root.left == null) {
            ret++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
        return ret;
    }

    //求第k层节点的个数
    public int getKleveNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKleveNodeCount(root.left, k - 1) + getKleveNodeCount(root.right, k - 1);
    }

    //获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;

        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1 : right + 1;
        //这个太耗费时间

    }

    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getHeight2(root.left) > getHeight2(root.right) ? getHeight2(root.left) + 1 : getHeight2(root.right) + 1;
        //这个太耗费时间

    }

    //检测value的元素是否存在
    public TreeNode find(TreeNode root, char value) {
        if (root == null) {
            return null;
        }
        if (root.val == value) {
            return root;
        }
        //左子树
        find(root.left, value);
        find(root.right, value);
        return null;
    }

    //相同的树
    //时间复杂度O(min(m,n)
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null || q == null && p != null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }

    //另一棵树的子树
    //时间复杂度O(s*t)
    //s  t

    public boolean isSubtree2(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree2(root.left, subRoot)) {
            return true;
        }
        if (isSubtree2(root.left, subRoot)) {
            return true;
        }
        return false;
    }


    //平衡二叉树
    //时间复杂度O（n^2）
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.abs(leftHeight - rightHeight) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return (left > right ? left : right) + 1;

    }

    //时间复杂度O(n)
    public boolean isBalanced2(TreeNode root) {
        if (root == null) return true;

        return maxDepth2(root) >= 0;
    }

    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        int leftH = maxDepth2(root.left);
        int rightH = maxDepth2(root.right);
        if (leftH >= 0 && rightH >= 0 && Math.abs(rightH - leftH) <= 1) {
            return Math.max(leftH, rightH) + 1;
        } else {
            return -1;
        }

    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        //使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val + " ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }

    }

    //力扣题：层序遍历
   /* public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new LinkedList();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//这一层的节点数
            List<Integer> list = new ArrayList<>();
            while(size != 0) {
                TreeNode top = queue.poll();
                //System.out.print(top.val + " ");//不进行打印了
                list.add(top.val);//因为list我们指定的是Integer的，但是这里的val放的是char类型，所以会报错
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
                size--;

            }
            ret.add(list);
        }
        return ret;
    } */

    //判断一个树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            //只要不为空我们就进来
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;//如果弹出的内容为空的话直接结束循环，判断队列中剩余元素是否都为空
            }
        }
            while(!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if(cur != null) {
                    //进来了就说明剩下的有不是null的，直接返回fales
                    return false;
                }
            }
        return true;
    }

    //二叉树的公共祖先
    /*
    根据二叉搜索树的特点
     */
    /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        //不为空的二叉树

        if(p == root || q == root) {
            //1.其中一个为根节点
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);//在root的坐树去找
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);//在root的右边去找

        if(leftRet != null && rightRet != null) {
            //p,q分别在root的左边和右边
            return root;
        } else if(leftRet != null) {
            //p，q在root的左边
            return leftRet;
        } else {
            //p，q在root的右边
            return rightRet;
        }
    }*/
    //二叉树的公共祖先
    //使用求链表的交点
}
